package com.yiwenup.sorting._07_shell;

import com.yiwenup.sorting.base.Sort;

import java.util.ArrayList;
import java.util.List;

/**
 * 希尔排序：底层是使用插入排序，用于消除逆序对，很适合，可以理解为是对插入排序的改进
 * 时间复杂度：最好 - O(n)；最坏(shell步长) - O(n²)；平均复杂度 - 【取决于步长】
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 **/
public class ShellSort<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void work() {
        List<Integer> stepSeq = generateStep();
        for (Integer step : stepSeq) {
            sort(step);
        }
    }

    /**
     * 分成 {@param step} 列排序
     */
    private void sort(int step) {
        for (int col = 0; col < step; col++) {
            for (int begin = col + step; begin < array.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }

    /**
     * 生成步长序列
     */
    private List<Integer> generateStep() {
        List<Integer> stepSeq = new ArrayList<>();

        int step = array.length;

        while ((step >>= 1) > 0) {
            stepSeq.add(step);
        }

        return stepSeq;
    }
}
